package peersim.graph;

import java.util.*;

/**
 * Contains static methods for wiring certain kinds of graphs. The general
 * contract of all methods is that they accept any graph and add edges
 * as specified in the documentation.
 */
public class GraphFactory {

    /** Disable instance construction */
    private GraphFactory() {
    }

// ===================== public static methods ======================
// ==================================================================
    /**
     * Wires a ring lattice.
     * The added connections are defined as follows. If k is even, links to
     * i-k/2, i-k/2+1, ..., i+k/2 are added (but not to i), thus adding an
     * equal number of predecessors and successors.
     * If k is odd, then we add one more successors than predecessors.
     * For example, for k=4: 2 predecessors, 2 successors.
     * For k=5: 2 predecessors, 3 successors.
     * For k=1: each node is linked only to its successor.
     * All values are understood mod n to make the lattice circular, where n is the
     * number of nodes in g.
     * @param g the graph to be wired
     * @param k lattice parameter
     * @return returns g for convenience
     */
    public static Graph wireRingLattice(Graph g, int k) {

        final int n = g.size();

        int pred = k / 2;
        int succ = k - pred;

        for (int i = 0; i < n; ++i) {
            for (int j = -pred; j <= succ; ++j) {
                if (j == 0) {
                    continue;
                }
                final int v = (i + j + n) % n;
                g.setEdge(i, v);
            }
        }
        return g;
    }

// -------------------------------------------------------------------
    /**
     * Watts-Strogatz model. A bit modified though: by default assumes a directed
     * graph. This means that directed
     * links are re-wired, and the undirected edges in the original (undirected)
     * lattice are modeled
     * by double directed links pointing in opposite directions. Rewiring is done
     * with replacement, so the possibility of wiring two links to the same target
     * is positive (though very small).
     * <p>
     * Note that it is possible to pass an undirected graph as a parameter. In that
     * case the output is the directed graph produced by the method, converted to
     * an undirected graph by dropping directionality of the edges. This graph is
     * still not from the original undirected WS model though.
     * @param g the graph to be wired
     * @param k lattice parameter: this is the out-degree of a node in the
     * ring lattice before rewiring
     * @param p the probability of rewiring each
     * @param r source of randomness
     * @return returns g for convenience
     */
    public static Graph wireWS(Graph g, int k, double p, Random r) {
//XXX unintuitive to call it WS due to the slight mods
        final int n = g.size();
        for (int i = 0; i < n; ++i) {
            for (int j = -k / 2; j <= k / 2; ++j) {
                if (j == 0) {
                    continue;
                }
                int newedge = (i + j + n) % n;
                if (r.nextDouble() < p) {
                    newedge = r.nextInt(n - 1);
                    if (newedge >= i) {
                        newedge++; // random _other_ node
                    }
                }
                g.setEdge(i, newedge);
            }
        }
        return g;
    }

// -------------------------------------------------------------------
    /**
     * Random graph. Generates randomly k directed edges out of each node.
     * The neighbors
     * (edge targets) are chosen randomly without replacement from the nodes of the
     * graph other than the source node (i.e. no loop edge is added).
     * If k is larger than N-1 (where N is the number of nodes) then k is set to
     * be N-1 and a complete graph is returned.
     * @param g the graph to be wired
     * @param k samples to be drawn for each node
     * @param r source of randomness
     * @return returns g for convenience
     */
    public static Graph wireKOut(Graph g, int k, Random r) {

        final int n = g.size();
        if (n < 2) {
            return g;
        }
        if (n <= k) {
            k = n - 1;
        }
        int[] nodes = new int[n];
        for (int i = 0; i < nodes.length; ++i) {
            nodes[i] = i;
        }
        for (int i = 0; i < n; ++i) {
            int j = 0;
            while (j < k) {
                int newedge = j + r.nextInt(n - j);
                int tmp = nodes[j];
                nodes[j] = nodes[newedge];
                nodes[newedge] = tmp;
                if (nodes[j] != i) {
                    g.setEdge(i, nodes[j]);
                    j++;
                }
            }
        }
        return g;
    }

// -------------------------------------------------------------------
    /**
     * A sink star.
     * Wires a sink star topology adding a link to 0 from all other nodes.
     * @param g the graph to be wired
     * @return returns g for convenience
     */
    public static Graph wireStar(Graph g) {

        final int n = g.size();
        for (int i = 1; i < n; ++i) {
            g.setEdge(i, 0);
        }
        return g;
    }

// -------------------------------------------------------------------
    /**
     * A regular rooted tree.
     * Wires a regular rooted tree. The root is 0, it has links to 1,...,k.
     * In general, node i has links to i*k+1,...,i*k+k.
     * @param g the graph to be wired
     * @param k the number of outgoing links of nodes in the tree (except
     * leaves that have zero out-links, and exactly one node that might have
     * less than k).
     * @return returns g for convenience
     */
    public static Graph wireRegRootedTree(Graph g, int k) {

        if (k == 0) {
            return g;
        }
        final int n = g.size();
        int i = 0; // node we wire
        int j = 1; // next free node to link to
        while (j < n) {
            for (int l = 0; l < k && j < n; ++l, ++j) {
                g.setEdge(i, j);
            }
            ++i;
        }
        return g;
    }

// -------------------------------------------------------------------
    /**
     * A hypercube.
     * Wires a hypercube.
     * For a node i the following links are added: i xor 2^0, i xor 2^1, etc.
     * this define a log(graphsize) dimensional hypercube (if the log is an
     * integer).
     * @param g the graph to be wired
     * @return returns g for convenience
     */
    public static Graph wireHypercube(Graph g) {

        final int n = g.size();
        if (n <= 1) {
            return g;
        }
        final int highestone = Integer.highestOneBit(n - 1); // not zero
        for (int i = 0; i < n; ++i) {
            int mask = highestone;
            while (mask > 0) {
                int j = i ^ mask;
                if (j < n) {
                    g.setEdge(i, j);
                }
                mask = mask >> 1;
            }

        }
        return g;
    }

// -------------------------------------------------------------------
    /**
     * This contains the implementation of the Barabasi-Albert model
     * of growing scale free networks. The original model is described in
     * <a href="http://arxiv.org/abs/cond-mat/0106096">
    http://arxiv.org/abs/cond-mat/0106096</a>.
     * It also works if the graph is directed, in which case the model is a
     * variation of the BA model
     * described in <a href="http://arxiv.org/pdf/cond-mat/0408391">
    http://arxiv.org/pdf/cond-mat/0408391</a>. In both cases, the number of the
     * initial set of nodes is the same as the degree parameter, and no links are
     * added. The first added node is connected to all of the initial nodes,
     * and after that the BA model is used normally.
     * @param k the number of edges that are generated for each new node, also
     * the number of initial nodes (that have no edges).
     * @param r the randomness to be used
     * @return returns g for convenience
     */
    public static Graph wireScaleFreeBA(Graph g, int k, Random r) {

        final int nodes = g.size();
        if (nodes <= k) {
            return g;
        }

        // edge i has ends (ends[2*i],ends[2*i+1])
        int[] ends = new int[2 * k * (nodes - k)];

        // Add initial edges from k to 0,1,...,k-1
        for (int i = 0; i < k; i++) {
            g.setEdge(k, i);
            ends[2 * i] = k;
            ends[2 * i + 1] = i;
        }

        int len = 2 * k; // edges drawn so far is len/2
        for (int i = k + 1; i < nodes; i++) // over the remaining nodes
        {
            for (int j = 0; j < k; j++) // over the new edges
            {
                int target;
                do {
                    target = ends[r.nextInt(len)];
                    int m = 0;
                    while (m < j && ends[len + 2 * m + 1] != target) {
                        ++m;
                    }
                    if (m == j) {
                        break;
                    }
                    // we don't check in the graph because
                    // this wire method should accept graphs
                    // that already have edges.
                } while (true);
                g.setEdge(i, target);
                ends[len + 2 * j] = i;
                ends[len + 2 * j + 1] = target;
            }
            len += 2 * k;
        }

        return g;
    }
// -------------------------------------------------------------------
/*
    public static void main(String[] pars) {

    int n = Integer.parseInt(pars[0]);
    //int k = Integer.parseInt(pars[1]);
    Graph g = new BitMatrixGraph(n);

    //wireWS(g,20,.1,new Random());
    //GraphIO.writeChaco(new UndirectedGraph(g),System.out);

    //wireScaleFreeBA(g,3,new Random());
    //wireKOut(g,k,new Random());
    //wireRegRootedTree(g,k);
    wireHypercube(g);
    GraphIO.writeNeighborList(g,System.out);
    }
     */
}
